import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.Vector;


public class Knapsack 
{
	private int numeroElementos;
	private int pesoMax;
	private Vector<Integer> utilidades;
	private Vector<Integer> pesos;
	private Vector<Integer> identificadores;
	Individuo melhorIndividuo;
	
	private int fitnessPiorIndividuo;
	private double fitnessMediaPopulacao;
	private int numeroIndividuosRepetidos;
	private int numeroIndCrossoverMelhores;
	private int numeroIndCrossoverPiores;
	
	/**
	 * Construtor.
	 * Le arquivo de entrada e preenche os vetores.
	 * @param arquivoEntrada
	 */
	public Knapsack(String arquivoEntrada)
    {
		// Inicializa atributos
		this.fitnessPiorIndividuo = 999999999;
		this.numeroIndividuosRepetidos = 0;
		this.numeroIndCrossoverMelhores = 0;
		this.numeroIndCrossoverPiores = 0;
		this.fitnessPiorIndividuo = -1;
		this.fitnessMediaPopulacao = 0.0;
		
		// Le arquivo de entrada
		if(arquivoEntrada.isEmpty())
		{
			System.out.println("Informe o nome do arquivo.");
			System.exit(0);
		}
		
		BufferedReader in;
		try 
		{
			in = new BufferedReader(new FileReader(arquivoEntrada));
			
			String line;
			StringTokenizer token;
			
			line = in.readLine();
			token = new StringTokenizer(line);
			
			this.numeroElementos = Integer.parseInt(token.nextToken());
			this.pesoMax = Integer.parseInt(token.nextToken());
			this.identificadores = new Vector<Integer>(this.numeroElementos);
	        
			// Preenche o vetor de ids dos objetos
			for(int i = 0; i < numeroElementos; i++)
				this.identificadores.add(i);
			
			// Obtem a lista de objetos
	    	line = in.readLine();
	    	token = new StringTokenizer(line);
	    	
	    	this.utilidades = new Vector<Integer>(this.numeroElementos);
	    	this.pesos = new Vector<Integer>(this.numeroElementos);
	    	
	    	while(token.hasMoreTokens())
	    	{
	    		utilidades.add(Integer.parseInt(token.nextToken()));
	    	}
	    	
	    	// Obtem a lista de pesos de cada objeto
	    	line = in.readLine();
	    	token = new StringTokenizer(line);
	    	
	    	while(token.hasMoreTokens())
	    	{
	    		pesos.add(Integer.parseInt(token.nextToken()));
	    	}
	    	
	    	in.close();
		}
		catch (FileNotFoundException e) 
		{
			System.out.println("Arquivo não encontrado: " + arquivoEntrada);
			e.printStackTrace();
		} 
		catch (IOException e) 
		{
			System.out.println("Erro ao ler linha do arquivo.");
			e.printStackTrace();
		}
    }
	
	
	public Populacao geraPopulacaoInicial(int nIndividuos, boolean repeticao)
	{
		Populacao inicial = new Populacao(nIndividuos);
		Individuo individuo = new Individuo(this.numeroElementos);
		
		Random rn = new Random();
		int r, somaPesos = 0;
		
		for (int i = 0; i < nIndividuos; i++)
		{
			individuo = new Individuo(this.numeroElementos);
			somaPesos = 0;
			
			for(int j = 0; j < this.numeroElementos; j++){
			
				r = rn.nextInt(this.numeroElementos);
				while(individuo.getIdentificadores().contains(r) && individuo.getIdentificadores().size() < this.numeroElementos)
					r = rn.nextInt(this.numeroElementos);
				
				if(somaPesos + this.pesos.get(r) <= this.pesoMax)
				{
					somaPesos += this.pesos.get(r);
					individuo.getIdentificadores().add(r);
				}
				else
					break;
			
			}

			boolean existeIndividuo = existeIndividuo(individuo, inicial);
			
			individuo.setFitness(this.calculaFitness(individuo));
			if(individuo.getFitness() > 0 && (repeticao || (!repeticao && !existeIndividuo)))
			{
				if(existeIndividuo)
					this.numeroIndividuosRepetidos++;
				inicial.getPopulacao().add(individuo);
			}
			else
				i--;
		}
		
		return inicial;
	}
	
	public int calculaFitness(Individuo ind)
	{
		int somaPesos = 0;
		int somaUtilidades = 0;
		
		for (Integer id : ind.getIdentificadores()) 
		{
			somaUtilidades += this.utilidades.get(id);
			somaPesos += this.pesos.get(id);
		}
		
		if(somaPesos <= pesoMax)
			return somaUtilidades;
		else
			return -somaPesos;
	}
	
	public double calculaFitnessMedia(Populacao p)
	{	
		for (Individuo ind : p.getPopulacao()) {
			this.fitnessMediaPopulacao += ind.getFitness();
		}
		
		this.fitnessMediaPopulacao = (this.fitnessMediaPopulacao/p.getPopulacao().size()); 
		
		return this.fitnessMediaPopulacao;
	}
	
	public void solve(BufferedWriter out, double[][] estatisticasPorGeracao, int tamPopulacao, int nGeracoes, int k, double probCrossover, 
					  double probMutacao, boolean elitismo, boolean repeticao) throws IOException
	{
		int melhorFitness = 0;
		int idMelhorIndividuo = 0;
		int fitnessX, fitnessY, fitnessMediaPais;
		boolean existeIndividuo;
		
		// Gera população inicial
		Populacao populacaoInicial = new Populacao(tamPopulacao);
		populacaoInicial.setPopulacao(this.geraPopulacaoInicial(tamPopulacao, repeticao).getPopulacao());
		
		// Busca o melhor entre a populacao inicial
		for (int i = 0; i < tamPopulacao; i++) 
		{
			Individuo ind = populacaoInicial.getPopulacao().get(i);
			if(ind.getFitness() > melhorFitness)
			{
				melhorFitness = ind.getFitness();
				idMelhorIndividuo = i;
			}
			if(ind.getFitness() < this.fitnessPiorIndividuo)
				this.fitnessPiorIndividuo = ind.getFitness();
		}
		
		this.melhorIndividuo = new Individuo(populacaoInicial.getPopulacao().get(idMelhorIndividuo));
		imprimeEstatisticas(out, 0, populacaoInicial);
		
		Individuo x, y, xAux, yAux;
		Random rand = new Random();
		Populacao geracaoAnterior = new Populacao(populacaoInicial);
		
		// Cria novas geracoes
		for(int j = 1; j < nGeracoes; j++)
		{
			Populacao novaGeracao = new Populacao(tamPopulacao);
			
			if(elitismo)
				novaGeracao.getPopulacao().add(this.melhorIndividuo);
			
			// Reinicializa as estatisticas
			this.numeroIndividuosRepetidos = 0;
			this.numeroIndCrossoverMelhores = 0;
			this.numeroIndCrossoverPiores = 0;
			this.fitnessPiorIndividuo = 999999999;
			melhorFitness = -1;
			
			// Preenche a nova populacao
			while(novaGeracao.getPopulacao().size() < tamPopulacao)
			{
				x = selecao(geracaoAnterior, k);
				y = selecao(geracaoAnterior, k);
				
				fitnessX = calculaFitness(x);
				fitnessY = calculaFitness(y);
				
				while(fitnessX < 0 || fitnessY < 0)
				{
					x = selecao(geracaoAnterior, k);
					y = selecao(geracaoAnterior, k);
					
					fitnessX = calculaFitness(x);
					fitnessY = calculaFitness(y);
				}
				
				// Crossover
				if(rand.nextDouble() <= probCrossover)
				{
					// Guarda os individuos originais caso seja necessario
					// refazer o crossover (se ambos passarem do peso maximo
					// apos a operacao)
					xAux = new Individuo(x);
					yAux = new Individuo(y);
					
					fitnessMediaPais = (fitnessX + fitnessY) / 2;
					
					crossover(x, y);
					
					fitnessX = calculaFitness(x);
					fitnessY = calculaFitness(y);
					
					while(fitnessX < 0 || fitnessY < 0)
					{
						x = new Individuo(xAux); 
						y = new Individuo(yAux);

						crossover(x, y);
						
						fitnessX = calculaFitness(x);
						fitnessY = calculaFitness(y);
					}
					
					// Recalcula estatistica de filhos melhores e piores
					if((fitnessX > fitnessMediaPais) && (fitnessX >= 0))
						this.numeroIndCrossoverMelhores++;
					else if((fitnessX < fitnessMediaPais) && (fitnessX >= 0))
						this.numeroIndCrossoverPiores++;
					
					if((fitnessY > fitnessMediaPais) && (fitnessY >= 0))
						this.numeroIndCrossoverMelhores++;
					else if((fitnessY < fitnessMediaPais) && (fitnessY >= 0))
						this.numeroIndCrossoverPiores++;
				}
				
				// Mutacao
				if(rand.nextDouble() <= probMutacao)
				{
					// Guarda os individuos originais caso seja necessario
					// refazer a mutacao (se passar do peso maximo
					// apos a operacao)
					xAux = new Individuo(x); 
					yAux = new Individuo(y);
					
					mutacao(x);
					while(calculaFitness(x) < 0)
					{
						x = new Individuo(xAux);
						mutacao(x);
					}
					
					mutacao(y);
					while(calculaFitness(y) < 0)
					{
						y = new Individuo(yAux);
						mutacao(y);
					}
				}
				
				x.setFitness(calculaFitness(x));
				y.setFitness(calculaFitness(y));
				
				// Recalcula melhor individuo
				if(x.getFitness() > melhorFitness)
				{
					melhorFitness = x.getFitness();
					this.melhorIndividuo = new Individuo(x);
				}
				if(y.getFitness() > melhorFitness)
				{
					melhorFitness = y.getFitness();
					this.melhorIndividuo = new Individuo(y);
				}
				
				// Recalcula fitness do pior individuo
				if((x.getFitness() < this.fitnessPiorIndividuo) && x.getFitness() >= 0)
					this.fitnessPiorIndividuo = x.getFitness();
				if((y.getFitness() < this.fitnessPiorIndividuo) && y.getFitness() >= 0)
					this.fitnessPiorIndividuo = y.getFitness();
				
				existeIndividuo = existeIndividuo(x, novaGeracao);
				
				// Adiciona o individuo na populacao se sua fitness for positiva e 
				// se e permitido ter individuos repetidos na populacao (ou nao e
				// permitido e esse individuo nao existia anteriormente)
				if(x.getFitness() >= 0 && 
						(repeticao || 
								(!repeticao && !existeIndividuo)))
				{
					if(existeIndividuo)
						this.numeroIndividuosRepetidos++;
					novaGeracao.getPopulacao().add(x);
				}
				
				existeIndividuo = existeIndividuo(y, novaGeracao);
				
				if(y.getFitness() >= 0 && 
						(repeticao || 
								(!repeticao && !existeIndividuo))
						&& (novaGeracao.getPopulacao().size() < tamPopulacao))
				{
					if(existeIndividuo)
						this.numeroIndividuosRepetidos++;
					novaGeracao.getPopulacao().add(y);
				}
			}
			
			// Armazena estatísticas
			estatisticasPorGeracao[j][0] += this.melhorIndividuo.getFitness();
			estatisticasPorGeracao[j][1] += this.fitnessPiorIndividuo;
			estatisticasPorGeracao[j][2] += calculaFitnessMedia(novaGeracao); 
			estatisticasPorGeracao[j][3] += this.numeroIndividuosRepetidos;
			estatisticasPorGeracao[j][4] += this.numeroIndCrossoverMelhores;
			estatisticasPorGeracao[j][5] += this.numeroIndCrossoverPiores;
			
			imprimeEstatisticas(out, j, novaGeracao);
			geracaoAnterior = new Populacao(novaGeracao);
		}
		
		out.write("\n\n******************************************************************************\n\n\n");
	}
	
	public Individuo selecao(Populacao p, int k)
	{
		Individuo melhorIndividuo = new Individuo(numeroElementos);
		Random rn = new Random();
		int r;
		
		for(int i = 0; i < k; i++)
		{
			r = rn.nextInt(p.getPopulacao().size());
			if(p.getPopulacao().get(r).getFitness() > melhorIndividuo.getFitness())
				melhorIndividuo = new Individuo(p.getPopulacao().get(r));
		}
		
		return melhorIndividuo;
	}
	
	public void crossover(Individuo x, Individuo y)
	{
		Random r = new Random();
		int posX = 0, posY = 0;
		int xSize, ySize;
		
		posX = r.nextInt(x.getIdentificadores().size() + 1);
		posY = r.nextInt(y.getIdentificadores().size() + 1);
		while((posX == 0 && posY == y.getIdentificadores().size())
				|| (posY == 0 && posX == x.getIdentificadores().size()))
		{
			posX = r.nextInt(x.getIdentificadores().size() + 1);
			posY = r.nextInt(y.getIdentificadores().size() + 1);
		}
		
		Vector<Integer> xAux = new Vector<Integer>(y.getIdentificadores().capacity());
		Vector<Integer> yAux = new Vector<Integer>(x.getIdentificadores().capacity());
		
		xSize = y.getIdentificadores().size() - posY + posX;
		ySize = x.getIdentificadores().size() - posX + posY;
		
		// Altera o indivíduo X
		for(int i = 0; i < xSize; i++)
		{
			if(i < posX)
				xAux.add(x.getIdentificadores().get(i));
			else if (!xAux.contains(y.getIdentificadores().get(i-posX + posY)))
				xAux.add(y.getIdentificadores().get(i-posX + posY));
		}
		
		// Altera o indivíduo Y
		for(int i = 0; i < ySize; i++)
		{
			if(i < posY)
				yAux.add(y.getIdentificadores().get(i));
			else if (!yAux.contains(x.getIdentificadores().get(i-posY + posX)))
				yAux.add(x.getIdentificadores().get(i-posY + posX));
		}
		
		x.setIdentificadores(xAux);
		y.setIdentificadores(yAux);
	}
	
	public void mutacao(Individuo x)
	{
		Random rn = new Random();
		int nMutacoes, posMutacionada, novoId;
		double pctMutacoes = 0.03;
		
		nMutacoes = (int)Math.ceil(pctMutacoes * x.getIdentificadores().size());
		
		int i = 0;
		while(i < nMutacoes)
		{
			posMutacionada = rn.nextInt(x.getIdentificadores().size());
			novoId = rn.nextInt(identificadores.size());
			if(!x.getIdentificadores().contains(identificadores.get(novoId)))
			{
				x.getIdentificadores().set(posMutacionada, novoId);
				i++;
			}
		}
	}
	
	private boolean existeIndividuo(Individuo x, Populacao p)
	{
		Object[] a, b;
		
		for (Individuo ind : p.getPopulacao()) 
		{
			if(ind.getFitness() == x.getFitness())
			{
				a = ind.getIdentificadores().toArray();
				b = x.getIdentificadores().toArray();
				Arrays.sort(a);
				Arrays.sort(b);
				
				if(Arrays.equals(a, b))
					return true;
			}
		}
		
		return false;
	}
	
	public void imprimeSolucao()
	{
		int somaUtilidades = 0, somaPesos = 0;
		
		System.out.println("Melhor indivíduo (ids): ");
		for (Integer id : this.melhorIndividuo.getIdentificadores()) 
		{
			System.out.print(id + " ");
		}
		System.out.println("\n");
		
		System.out.println("Utilidades: ");
		for(int i = 0; i < this.melhorIndividuo.getIdentificadores().size(); i++)
		{
			somaUtilidades += this.utilidades.get(this.melhorIndividuo.getIdentificadores().get(i));
			System.out.print(this.utilidades.get(this.melhorIndividuo.getIdentificadores().get(i)) + " ");
		}
		System.out.println("\n");
		
		System.out.println("Pesos: ");
		for(int i = 0; i < this.melhorIndividuo.getIdentificadores().size(); i++)
		{
			somaPesos += this.pesos.get(this.melhorIndividuo.getIdentificadores().get(i));
			System.out.print(this.pesos.get(this.melhorIndividuo.getIdentificadores().get(i)) + " ");
		}
		System.out.println("\n");
		
		System.out.println("Fitness: " + somaUtilidades);
		System.out.println("Soma dos pesos: " + somaPesos);
	}
	
	private void imprimeEstatisticas(BufferedWriter out, int geracao, Populacao p) throws IOException
	{
		int somaUtilidades = 0, somaPesos = 0;
		out.write("Geração: " + (geracao + 1) + "\n");
		out.write("Fitness do melhor indivíduo: " + melhorIndividuo.getFitness() + "\n");
		out.write("Fitness do pior indivíduo: " + this.fitnessPiorIndividuo + "\n");
		out.write("Fitness média da população: " + calculaFitnessMedia(p) + "\n");
		out.write("Número de indivíduos repetidos na população: " + this.numeroIndividuosRepetidos + "\n");
		out.write("Número de indivíduos gerados por crossover melhores que a fitness média dos pais: " + this.numeroIndCrossoverMelhores + "\n");
		out.write("Número de indivíduos gerados por crossover piores que a fitness média dos pais: " + this.numeroIndCrossoverPiores + "\n\n");
		
		out.write("Melhor indivíduo (ids): ");
		for (Integer id : this.melhorIndividuo.getIdentificadores()) 
		{
			out.write(id + " ");
		}
		out.write("\n\n");
		
		out.write("Utilidades: ");
		for(int i = 0; i < this.melhorIndividuo.getIdentificadores().size(); i++)
		{
			somaUtilidades += this.utilidades.get(this.melhorIndividuo.getIdentificadores().get(i));
			out.write(this.utilidades.get(this.melhorIndividuo.getIdentificadores().get(i)) + " ");
		}
		out.write("\n\n");
		
		out.write("Pesos: ");
		for(int i = 0; i < this.melhorIndividuo.getIdentificadores().size(); i++)
		{
			somaPesos += this.pesos.get(this.melhorIndividuo.getIdentificadores().get(i));
			out.write(this.pesos.get(this.melhorIndividuo.getIdentificadores().get(i)) + " ");
		}
		out.write("\n\n");
		
		out.write("Fitness: " + somaUtilidades + "\n\n");
		out.write("Soma dos pesos: " + somaPesos + "\n\n\n\n");
	}
	
	/**
	 * @return the melhorIndividuo
	 */
	public Individuo getMelhorIndividuo() {
		return melhorIndividuo;
	}


	/**
	 * @param melhorIndividuo the melhorIndividuo to set
	 */
	public void setMelhorIndividuo(Individuo melhorIndividuo) {
		this.melhorIndividuo = melhorIndividuo;
	}


	/**
	 * @return the fitnessPiorIndividuo
	 */
	public int getFitnessPiorIndividuo() {
		return fitnessPiorIndividuo;
	}


	/**
	 * @param fitnessPiorIndividuo the fitnessPiorIndividuo to set
	 */
	public void setFitnessPiorIndividuo(int fitnessPiorIndividuo) {
		this.fitnessPiorIndividuo = fitnessPiorIndividuo;
	}


	/**
	 * @return the fitnessMediaPopulacao
	 */
	public double getFitnessMediaPopulacao() {
		return fitnessMediaPopulacao;
	}


	/**
	 * @param fitnessMediaPopulacao the fitnessMediaPopulacao to set
	 */
	public void setFitnessMediaPopulacao(int fitnessMediaPopulacao) {
		this.fitnessMediaPopulacao = fitnessMediaPopulacao;
	}


	/**
	 * @return the numeroIndividuosRepetidos
	 */
	public int getNumeroIndividuosRepetidos() {
		return numeroIndividuosRepetidos;
	}


	/**
	 * @param numeroIndividuosRepetidos the numeroIndividuosRepetidos to set
	 */
	public void setNumeroIndividuosRepetidos(int numeroIndividuosRepetidos) {
		this.numeroIndividuosRepetidos = numeroIndividuosRepetidos;
	}


	/**
	 * @return the numeroIndCrossoverMelhores
	 */
	public int getNumeroIndCrossoverMelhores() {
		return numeroIndCrossoverMelhores;
	}


	/**
	 * @param numeroIndCrossoverMelhores the numeroIndCrossoverMelhores to set
	 */
	public void setNumeroIndCrossoverMelhores(int numeroIndCrossoverMelhores) {
		this.numeroIndCrossoverMelhores = numeroIndCrossoverMelhores;
	}


	/**
	 * @return the numeroIndCrossoverPiores
	 */
	public int getNumeroIndCrossoverPiores() {
		return numeroIndCrossoverPiores;
	}


	/**
	 * @param numeroIndCrossoverPiores the numeroIndCrossoverPiores to set
	 */
	public void setNumeroIndCrossoverPiores(int numeroIndCrossoverPiores) {
		this.numeroIndCrossoverPiores = numeroIndCrossoverPiores;
	}	
}
